package InterviewsExposed;

public class LinkedListOperations {
	
	/*
	 * Receives the head of a Single Linked List and insert an element in the front.
	 */
	public static ListElement insertInFront(ListElement list, Object data){
		
		ListElement temp = new ListElement(data);
		temp.next = list;
		
		return temp;
	}
	
	/*
	 * Finds an element in the list and returns it
	 */
	public static ListElement find(ListElement head, Object data){
		
		while (head != null && head.getData() != data){
			
			head = head.next;
		}
		
		return head;
	}
	
	/*
	 * Deletes and element
	 */
	public static ListElement delete(ListElement head, ListElement deleteMe){
		
		ListElement run = head;
		
		//Special case for the head
		if (deleteMe.getData() == head.getData()){
			head = run.next;
			return head;
		}
		else{
			
			while (run.next != null){
				if (run.next.getData() == deleteMe.getData()){
					run.next = run.next.next;
				}
				run = run.next;
			}
		}
		
		return head;
	}
	
	public static void printLinkedList(ListElement head){
		int i = 1;
		if (head == null){
			System.out.println("------- Start of the List ---------");
			System.out.println("Empty list");
			System.out.println("------- End of the List -----------");
		}
		else{
			System.out.println("------- Start of the List ---------");
			while (head != null){
				
				System.out.println("Element " + i + " : " + head.getData());
				i++;
				head = head.next;
			}
			System.out.println("------- End of the List -----------");
		}
	}
	
	public static ListElement insertAtEnd(ListElement head, Object data){
		
		ListElement run = head;
		if (head == null || head.getData() == null){
			head = new ListElement(data);
		}
		else{
			while (run.next != null){
				run = run.next;
			}
			run.next = new ListElement(data);
		}
		
		return head;
	}
	
	public static ListElement reverseTheList(ListElement head){
		
		return reversingList(head, null);
	}
	
	private static ListElement reversingList(ListElement aNode, ListElement previousNode){
		ListElement temp;
		if (aNode.next == null){
			aNode.next = previousNode;
			return previousNode.next;
		}
		else{
			temp = reversingList(aNode.next, aNode);
			aNode.next = previousNode;
			return temp;
		}
	}
	
	public static ListElement reverseTheListNoRecursive(ListElement head){
		
		ListElement reversed = null;
		while (head != null){
			ListElement temp = new ListElement(head.getData());
			temp.next = reversed;
			reversed = temp;
			head = head.next;
		}
		
		return reversed;
	}
	
	public static boolean checkCycling(ListElement head){
		
		
		
		return false;
	}
	
	public static ListElement createCycledList(){
		
		ListElement head = new ListElement();
		ListElement cicle = new ListElement(4);
		
		head = LinkedListOperations.insertAtEnd(head, 1);
		head = LinkedListOperations.insertAtEnd(head, 2);
		head = LinkedListOperations.insertAtEnd(head, 3);
		
		ListElement run = head;
		
		while (run.next != null){
			
			if (run.getData() == (Object)2){
				cicle.next = run;
			}
			run = run.next;
		}
		run.next = cicle;
		
		return head;
	}
	
	public static boolean isListCycled(ListElement head){
		
		ListElement runFast = head;
		
		ListElement runSlow = head;
		
		runFast = runFast.next;
		
		while (true){
			
			if (runFast == null)
				return false;
			else
			if (runFast == runSlow){
				return true;
			}
			else{
				runFast = runFast.next.next;
				runSlow = runSlow.next;
			}
		}
		
	}
}
